FFT Butterfly Algorithm Explorer

Interactive Cooley–Tukey Decimation-in-Time (DIT) Signal Flow Graph.

FFT Size (N):

How it Works

The Cooley–Tukey algorithm recursively breaks down a Discrete Fourier Transform (DFT) of size N into two smaller DFTs of size N/2.

Key Concepts:

Bit-Reversal: Notice the inputs on the left x[n]. They are not in order (0, 1, 2...). They are bit-reversed to allow in-place computation.
Stages: There are exactly log₂(N) stages of computation.
The Butterfly (✖): Two inputs combine to create two outputs.

Top Output: A + W · B
Bottom Output: A − W · B
Twiddle Factor: The complex exponential multiplier W_N^k applied to the bottom branch.

Interactive Mode:
Hover your mouse over any node to trace its dependency path backward.

Signal Flow Graph

Data Path Multiplier (W_N^k) Subtraction (−1)